/**
 * 35. Search Insert Position
 * https://leetcode.com/problems/search-insert-position/
 */
package lc35;

public class Main {
  public static void main(String[] args) {
    int[] nums = {1,2,4,5};
    int target = 3;
    int i = new Solution().searchInsert(nums, target);
    System.out.println(i);
  }
}

class Solution {
  public int searchInsert(int[] nums, int target) {
    int n = nums.length;
    if (target <= nums[0]) return 0;
    if (target > nums[n - 1]) return n;
    if (target == nums[n - 1]) return n - 1;

    int left = 0;
    int right = n;
    while (left < right - 1) {
      int m = (right - left) / 2 + left;
      if (target < nums[m]) right = m;
      else if (target > nums[m]) left = m;
      else return m;
    }

    return right;
  }
}
